#include <bits/stdc++.h>
using namespace std;
//typedef long long int;
const int INF = 0x3f3f3f3f;
int n, m;
int d[15][1<<12], G[15][15];
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    memset(d, INF, sizeof d), memset(G, INF, sizeof G);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b, w; cin >> a >> b >>w;
        G[b][a] = G[a][b] = min(G[a][b], w);
    }
    for (int i = 1; i <= n ; ++i) {
        d[1][1<<(i-1)] = 0;
    }
    for (int i = 2; i <= n ; ++i) {
        for (int s = 0; s < 1<<n; ++s) {
            for (int ss = (s-1)&s; ss != 0 ; ss = (ss-1)&s) {
                if(d[i-1][ss] == INF) continue;
                int t = s^ss; 
                int inc = 0;
                bool flg = true;
                for (int v = 1; v <= n ; ++v) {
                    if((1<<(v-1) & t) == 0) continue;
                    int tmp = INF;
                    for (int u = 1; u <= n ; ++u) {
                        if((1<<(u-1) & ss) == 0) continue;
                        tmp = min(tmp, G[u][v]);
                    }
                    if(tmp == INF) {flg = false; break;}
                    inc += tmp;
                }
                if(!flg) continue;
                inc *= i-1;
                d[i][s] = min(d[i][s], d[i-1][ss] + inc);
            }
        }
    }

    int ans = INF;
    for (int i = 1; i <= n; ++i) {
        ans = min(ans, d[i][(1<<n)-1]);
    }
    cout << ans;
    return 0;
}